<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 判断链表是否有环可以通过快慢指针的方式。fast每次走两步，slow走一步，如果链表有环，那么fast就一定会追上slow
      因为相对于slow来说，fast在环里是一步步的追slow的。
      那么相遇可以判断出来。如何判断相遇的那个点呢？
      只需要让fast重新变到头节点，slow和fast每个都只走一步，相遇时就是环形的入口
      因为x=(n-1)y+z。x是头到入口 z是相遇点到入口。所以只需要再走一圈，x，z就是相等的，让他们都只走一步即可
      */
      var detectCycle = function (head) {
        let fast = head;
        let slow = head;
        while (fast && fast.next) {
          fast = fast.next.next;
          slow = slow.next;
          if (fast == slow) {
            fast = head;
            while (slow != fast) {
              fast = fast.next;
              slow = slow.next;
            }
            return slow;
          }
        }
        return null;
      };
    </script>
  </body>
</html>
